package cn.xkai.exercise.a;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @description: 两个数组的交集 II
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 1000
 * <p>
 * 自己的思路：未完成
 * 借鉴的思路：先排序，从头部依次判断相同部分元素
 * 进阶：hashmap、双指针
 * @author: kaixiang
 * @date: 2022-07-04
 **/
public class Solution27 {
    public int[] intersect(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int len = Math.min(len1, len2);
        int[] ans = new int[len];
        if (len1 == 0 || len2 == 0) {
            return ans;
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0, k = 0;
        while (i < len1 && j < len2) {
            if (nums1[i] == nums2[j]) {
                ans[k++] = nums1[i];
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return Arrays.copyOfRange(ans, 0, k);
    }

    public int[] intersectHashMap(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num1 : nums1) {
            map.put(num1, map.getOrDefault(num1, 0) + 1);
        }
        int n = Math.min(nums1.length, nums2.length);
        int[] res = new int[n];
        int i = 0;
        for (int num2 : nums2) {
            if (map.getOrDefault(num2, 0) > 0) {
                res[i++] = num2;
                map.put(num2, map.get(num2) - 1);
            }
        }
        return Arrays.copyOf(res, i);
    }

    public static void main(String[] args) {

    }
}
